import java.util.*;

class CoalitionValue{
	TreeSet<Integer> coalition;
	boolean wins;
	public CoalitionValue(){
		coalition = null;
		wins = true;
	}
	@Override
	public boolean equals(Object o){
		TreeSet<Integer> arg1 = ((CoalitionValue) o).coalition;
		TreeSet<Integer> arg0 = this.coalition;

		if(!(arg0.size() == arg1.size()))
			return false;

		Iterator<Integer> it = arg1.iterator();
		int j;
		for(int i:arg0){
			j = it.next();
			if(!(i==j))
				return false;
		}
		return true;
	}
}

class MyComparator implements Comparator<TreeSet<Integer>>{

	public int compare(TreeSet<Integer> arg0, TreeSet<Integer> arg1) {
		if(arg0.size() > arg1.size())
			return 1;
		if(arg0.size() < arg1.size())
			return -1;
		
		Iterator<Integer> it = arg1.iterator();
		int j;
		for(int i:arg0){
			j = it.next();
			if(i>j)
				return 1;
			if(i<j)
				return -1;
		}
		return 0;
	}//compare
	
}//comparatore

class Utility{
	public static int set(int mb, int offset, boolean b){
		int mask = 1<<offset;
		return mb | mask;
	}
	public static boolean get(int mb, int offset){
		int mask = 1<<offset;
		mb = mb & mask;
		return !(mb==0);
	}
	public static int tsToInt(TreeSet<Integer> ts){
		int id=0;
		for(int i:ts)
			id = set(id, i, true);
		return id;
	}
	public static TreeSet<Integer> intToTs(int id){
		TreeSet<Integer> ts = new TreeSet<Integer>();
		int i=0;
		while(!(id==0)){
			if(get(id,0)) // id%2==0
				ts.add(i);
			id = id >>> 1;
			i++;
		}
		return ts;
	}
	public static void printCoalition(TreeSet<Integer> ts){
		System.out.print("{ ");
		for(int i:ts)
			System.out.print(i+" ");
		System.out.println("}");
	}
	public static void printCoalition(int id){
		System.out.print("{ ");
		int i = 0;
		while(!(id==0)){
			if(get(id,0))
				System.out.print(i+" ");
			i++;
			id = id >>> 1;
		}
		System.out.println("}");		
	}
}

@SuppressWarnings("unused")
public class ProvaStruttureDati {
	
	public static void generateSubsets(){
		TreeSet<Integer> ts = new TreeSet<Integer>();
		generateSubsetsRec(ts, -1, NUM_PLAYER);
	}
	
	public static void generateSubsetsRec(TreeSet<Integer> ts, int start, int max){
		TreeSet<Integer> tsNew = new TreeSet<Integer>(ts);
		if(start > -1)
			tsNew.add(start);
		Utility.printCoalition(tsNew);
		start++;
		for(int i=start; i<max; i++)
			generateSubsetsRec(tsNew, i, max);
	}
	

	private static void generateSubsets(LinkedList<CoalitionValue> sd) {
		CoalitionValue cv;
		for(int i=0; i<NUM_COALITION; i++){
			cv = new CoalitionValue();
			cv.coalition = Utility.intToTs(i);
			sd.add(cv);
		}			
	}

	private static void generateSubsets(boolean[] sd) {
		for(int i=0; i<NUM_COALITION; i++)
			sd[i] = true;
	}

	private static void generateSubsets(int[] sd) {
		int base;
		int offset;
		for(int i=0; i<NUM_COALITION; i++){
			base = i>>>5;
			offset = i & 31;
			Utility.set(sd[base], offset, true);
		}
	}

	private static void generateSubsets(TreeMap<TreeSet<Integer>, Boolean> sd) {
		TreeSet<Integer> ts;
		for(int i=0; i<NUM_COALITION; i++){
			ts = Utility.intToTs(i);
			sd.put(ts, true);
		}
	}
	
	private static boolean getValue(LinkedList<CoalitionValue> sd, int q) {
		TreeSet<Integer> ts = Utility.intToTs(q);
		CoalitionValue cv = new CoalitionValue();
		cv.coalition = ts;
		return sd.get(sd.indexOf(cv)).wins;
	}

	private static boolean getValue(TreeMap<TreeSet<Integer>, Boolean> sd, int q) {
		TreeSet<Integer> ts = Utility.intToTs(q);
		return sd.get(ts);
	}

	private static boolean getValue(boolean[] sd, int q) {
		return sd[q];
	}

	private static boolean getValue(int[] sd, int q) {
		int base = q>>>5;
		int offset = q & 31;
		return Utility.get(sd[base], offset);
	}

	public static final int NUM_PLAYER = 20;
	public static final int NUM_COALITION = 1<<NUM_PLAYER;
	public static final int NUM_QUERY = 1000;


	@SuppressWarnings("resource")
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);

		int query;
		long time_build;
		long time_query;
		
		System.out.println("Gioco con "+NUM_PLAYER+" giocatori e, quindi,"+ NUM_COALITION + " coalizioni");
		System.out.print("Scrivi qualcosa per continuare: ");sc.next();
		
		/*
		//Prova algoritmo ricorsivo
		generateSubsets();
		if(true) System.exit(0);
		/* */
		
		time_build = System.currentTimeMillis();
		
		
		/*
		//Soluzione 1: LinkedList
		LinkedList<CoalitionValue> sd = new LinkedList<CoalitionValue>();
		/**/

		/*
		//Soluzione 2: TreeMap
		TreeMap<TreeSet<Integer>, Boolean> sd = new TreeMap<TreeSet<Integer>, Boolean>(new MyComparator());
		/**/

		
		//Soluzione 3: Array Statico di Boolean
		//boolean[] sd = new boolean[NUM_COALITION];
		/**/

		
		//Soluzione 4: Array Statico di bit
		int[] sd = new int[(int) Math.ceil(NUM_COALITION/32)];
		/**/
		
		/*
		//Soluzione 5: Array Statico di bit
		CoalitionValue[] sd = new CoalitionValue[NUM_COALITION];
		/**/
				
		generateSubsets(sd);
		
		time_build = System.currentTimeMillis() - time_build;

		System.out.println("Struttura dati inizializzata");
		System.out.print("Scrivi qualcosa per continuare: ");sc.next();
		
		
		System.out.print("Eseguo "+ NUM_QUERY +" interrogazioni casuali sulla struttura dati..."); System.out.flush();
		
		time_query = System.currentTimeMillis();

		for(int q = 0; q<NUM_QUERY; q++){
			query = (int) (Math.random()*NUM_COALITION);
			getValue(sd, query);
		}

		time_query = System.currentTimeMillis() - time_query;
		
		
		System.out.println("Resoconto:");
		System.out.println("\tTempo di costruzione: " + time_build);
		System.out.println("\tTempo di risposta: " + time_query);
		System.out.print("Scrivi qualcosa per continuare: ");sc.next();
		
	}

}
